//
//  trie.h
//  utilities
//
//  Created by Sam Jaffe on 12/12/12.
//  Copyright (c) 2012 Sam Jaffe. All rights reserved.
//

#pragma once

#include <cstring>
#include <iostream>
#include <memory>
#include <unordered_map>

template <class C, class V>
class trie : private std::unordered_map<C, std::shared_ptr<trie<C, V> > > {
private:
    typedef trie<C, V> _Self;
    typedef std::unordered_map<C, std::shared_ptr<trie<C, V> > > _Super;
public:
    
    V& operator ()() {
        return value;
    }
    
    const V& operator ()() const {
        return value;
    }
    
    template <typename T>
    V& operator[](const T& arr) {
        return _bracket(std::begin(arr), std::end(arr));
    }
    
    template <typename T>
    const V& operator[](const T& arr) const {
        return _bracket(std::begin(arr), std::end(arr));
    }
private:
    static const V default_value;
    V value;
    
    template <typename InputIt>
    V& _bracket(InputIt it, const InputIt end) {
        if (it == end) {
            return value;
        } else {
            return init(*it)->_bracket(++it, end);
        }
    }
    
    template <typename InputIt>
    const V& _bracket(InputIt it, const InputIt end) const {
        if (it == end) {
            return value;
        } else {
            return init(*it)->_bracket(++it, end);
        }
    }
    
    std::shared_ptr<_Self> init(const C& c) {
        auto ret = _Super::operator[](c);
        if (ret == nullptr) {
            ret = _Super::operator[](c) = std::make_shared<_Self>();
        }
        return ret;
    }
};
